package util;

public class BinarySearchTree {
	private Node root;

	public BinarySearchTree() {
		root=null;
	}	
	public void add(Comparable obj){
		Node node=new Node(obj, null, null);
		if(root==null) root=node;
		else root.addNode(node);
	}
	public Node find(Comparable obj){
		Node current=root;
		while(current!=null){
			int comp=obj.compareTo(current.getData());
			if(comp==0) return current;
			else if(comp<0) return current.getLeft();
			else return current.getRight();
		}
		return null;
	}
	public boolean remove(Comparable obj){
		Node removedNode=root;
		Node parent=null;
		boolean found=false;
		while(!found && removedNode!=null){
			int comp=obj.compareTo(removedNode.getData());
			if(comp==0) found=true;
			else{
				parent=removedNode;
				if(comp<0) removedNode=removedNode.getLeft();
				else removedNode=removedNode.getRight();
			}
		}
		if(!found) return false;
		if(removedNode.getLeft()==null || removedNode.getRight()==null){
			Node newChild=null;
			if(removedNode.getLeft()==null){
				newChild=removedNode.getRight();
			}
			else{
				newChild=removedNode.getLeft();
			}
			if(parent!=null){
				if(parent.getLeft()==removedNode){
					parent.setLeft(newChild);
				}
				else if(parent.getRight()==removedNode){
					parent.setRight(newChild);
				}
			}
			else{
				root=newChild;
			}
			return true;
		}
		else{
			Node smallestParent=removedNode;
			Node smallest=removedNode.getRight();
			while(smallest.getLeft()!=null){
				smallestParent=smallest;
				smallest=smallest.getLeft();
			}
			removedNode.setData(smallest.getData());
			smallestParent.setLeft(smallest.getLeft());
			return true;			
		}

	}

}
